package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/9/7 11:02 上午
 * <p>
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 * <p>
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 */
public class GenerateParenthesis {

    public static void main(String[] args) {

        GenerateParenthesis exe = new GenerateParenthesis();
        List<String> res = exe.generateParenthesis(3);

        int i = 0;
    }

    public List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList<>();


        List<String> tempList = new ArrayList<>();

        int left = n;
        int right = n;

        backtrack(res, tempList, n, n);

        return res;

    }

    String[] chArr = new String[]{"(", ")"};

    private void backtrack(List<String> res, List<String> tempList, int left, int right) {


        // 若左括号剩下的多，说明不合法
        if (left > right) {
            return;
        }

        // 数量⼩于 0 肯定是不合法的
        if (left < 0 || right < 0) {
            return;
        }

        //终止条件
        if (left == 0 && right == 0) {
            res.add(String.join("", tempList));
            return;
        }


        //循环 选择列表
        for (String str : chArr) {
            if (str.equals("(")) {
                tempList.add(str);
                backtrack(res, tempList, left - 1, right);
            } else if (str.equals(")")) {
                tempList.add(str);
                backtrack(res, tempList, left, right - 1);
            }
            //撤销选择
            tempList.remove(tempList.size() - 1);

        }

    }

}
